package 链表相交;

import 删除链表的倒数第N个结点.Demo19;
import 翻转链表.Demo206;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 相交链表
 * @date 2022/10/15 15:33
 */
public class Demo160 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode preA=new ListNode(-1);
        ListNode curA=preA;
        preA.next=headA;
        ListNode preB=new ListNode(-1);
        ListNode curB=preB;
        preB.next=headB;
        int countA=0;
        int countB=0;
        while (preA.next!=null){
            preA=preA.next;
            countA++;
        }
        while (preB.next!=null){
            preB=preB.next;
            countB++;
        }
        //如果是A长的话，A先走N步
        if(countA>countB){
            int length=countA-countB;
            while (length>0&&curA!=null){
                curA=curA.next;
                length--;
            }
        }else {
            int length=countB-countA;
            while (length>0&&curB!=null){
                curB=curB.next;
                length--;
            }
        }
        while (curB!=null&&curA!=null){
            if(curB==curA){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}
